/**
 * 
 */
package linkedlist.passed2;

import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author michael
 *Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
 */
public class MergeKSortedLists {

	
	/**
	 * Definition for singly-linked list.
	 * public class ListNode {
	 *     int val;
	 *     ListNode next;
	 *     ListNode(int x) {
	 *         val = x;
	 *         next = null;
	 *     }
	 * }
	 */
	
	
	/**
	 * 
	 */
	public MergeKSortedLists() {
		// TODO Auto-generated constructor stub
	}

    public ListNode mergeKLists(List<ListNode> lists) {
    	if (lists.size() == 0)
    		return null;
    	if (lists.size() == 1) 
    		return lists.get(0);
    	
    	PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.size(),
    			new Comparator<ListNode>() {
    		public int compare(ListNode l1, ListNode l2) {
    			return Integer.compare(l1.val, l2.val);
    		}});
    	
    	for (int i = 0; i < lists.size(); i++) {
    		if (lists.get(i) != null) {
    			queue.add(lists.get(i));
    		}
    	}
    	
    	ListNode newHead = new ListNode(0);
    	ListNode curr = newHead;
    	while (!queue.isEmpty()) {
    		ListNode node = queue.poll();
    		curr.next = node;
    		curr = curr.next;
    		if (node.next != null) {
    			queue.add(node.next);
    		}
    	}
    	
    	return newHead.next;
    }
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}
	
	 public class ListNode {
	      int val;
	      ListNode next;
	      ListNode(int x) {
	          val = x;
	          next = null;
	      }
	 }

}
